package com.example.demo.tixiban;

import java.util.Arrays;

/**
 * @author xujm
 * @version V2.4
 *
 *  如何只使用一个队列 完成排序?
 *  针对一个数组arr  011 021  112  122
 *  容易知道:
 *      011 021 个位数为1   112 122 个位数为2
 *      定义位数数组 count:  0  2  2  0  0  (个数)
 *                           0  1  2  3  4 (下标)
 *      将count转换成 小于等于下标有多少个数的 数组 count`: 0 2 4 4 4 (个数)
 *                                                          0 1 2 3 4 (下标)
 *     从右往左遍历arr,根据count`数组获取当前数字(数字对应位数的值) 在辅助数组help 中的位置
 *     122的获取到4，那么它占有的是0-3，由于从右往左遍历，那么占用help中3位置。 然后count`[2]--;
 *     help 数组遍历完了 赋值给arr，进行十位数的排序
 *
 *
 * @since 2.4.0 2022/3/20 13:29
 */
public class 基数排序 {


    public static void sort(int [] arr){

        int radix = 0;
        int [] help = new int [arr.length];
        int [] count = new int[10];
        int max = getMax(arr);
        while(max>0){

            for(int i=0;i<arr.length;i++){
                int wei  = getWei(arr[i],radix);
                count[wei]++;
            }
            for(int i=1;i<count.length;i++){
                count[i] = count[i-1]+count[i];
            }
            for(int i=arr.length-1;i>=0;i--){
                int wei = getWei(arr[i],radix);
                int index = count[wei]-1;//下标
                help[index] = arr[i];
                count[wei]--;
            }
            for(int i=0;i<help.length;i++){
                arr[i]=help[i];
            }
            radix++;
            max = max/10;
            Arrays.fill(count,0);
        }
    }

    public static int getWei(int value,int raidx){
        int temp = (int) Math.pow(10,raidx);
        return (value/temp) % 10;
    }


    public static int getMax(int [] arr){
        int max=0;
        for(Integer temp : arr){
            max = Math.max(temp,max);
        }
        return max;
    }

    public static void main(String[] args) {

        int [] arr = {15,231,34,551,875,761,1446};
        sort(arr);
        for(int i =0;i<arr.length;i++){
            System.out.print(arr[i]+" ");
        }
        // System.out.println(getWei(31,2));
    }






}
